{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Hamming Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hammingDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #汉明距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>两个整数之间的 <a href=\"https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB\">汉明距离</a> 指的是这两个数字对应二进制位不同的位置的数目。</p>\n",
    "\n",
    "<p>给你两个整数 <code>x</code> 和 <code>y</code>，计算并返回它们之间的汉明距离。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 1, y = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "1   (0 0 0 1)\n",
    "4   (0 1 0 0)\n",
    "       ↑   ↑\n",
    "上面的箭头指出了对应二进制位不同的位置。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 3, y = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= x, y <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hamming-distance](https://leetcode.cn/problems/hamming-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hamming-distance](https://leetcode.cn/problems/hamming-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n4', '3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        count = 0\n",
    "        a = x ^ y\n",
    "        while a > 0:\n",
    "            count += a & 1\n",
    "            a = a>>1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        binary_num ='{0:b}'.format(x^y)  # ‘b’ - 二进制。将数字以2为基数进行输出\n",
    "        return binary_num.count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        output = bin(x^y).count('1')\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        result = 0\n",
    "        while (x != 0 or y != 0):\n",
    "            if (x % 2 != y % 2):\n",
    "                 result += 1\n",
    "            x //= 2\n",
    "            y //= 2\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "\n",
    "        res = x ^ y \n",
    "\n",
    "        cnt = 0\n",
    "        while res != 0 :\n",
    "            res = res & (res-1)\n",
    "            cnt += 1\n",
    "        \n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        result = 0\n",
    "        while (x != 0 or y != 0):\n",
    "            if (x % 2 != y % 2):\n",
    "                 result += 1\n",
    "            x //= 2\n",
    "            y //= 2\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        z = x ^ y\n",
    "        ans = 0\n",
    "        while z:\n",
    "            ans += z & 1\n",
    "            z >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        n  = x ^ y\n",
    "        res = 0\n",
    "        for i in range(31):\n",
    "            res += (n >> i) & 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        s = x^y\n",
    "        num=0\n",
    "        while s :\n",
    "            s &= s-1\n",
    "            num +=1;\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        # return sum(map(int, bin(x ^ y).split('b')[-1]))\n",
    "\n",
    "        # return bin(x ^ y).count('1')\n",
    "\n",
    "        # a = x ^ y\n",
    "        # c = 0\n",
    "        # while a:\n",
    "        #     c += a & 1\n",
    "        #     a >>= 1\n",
    "        # return c\n",
    "\n",
    "        a = x ^ y\n",
    "        c = 0\n",
    "        while a:\n",
    "            c += 1\n",
    "            a &= a - 1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        # return bin(x^y).count('1')\n",
    "        ret = 0\n",
    "        # bin(x) 有前缀\"0b\"\n",
    "        bx, by = bin(x)[2:].zfill(32), bin(y)[2:].zfill(32)\n",
    "        for i in range(32):\n",
    "            if bx[i] != by[i]:\n",
    "                ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        res = 0\n",
    "        tmp = x^y\n",
    "        while tmp > 0:\n",
    "            res += (tmp & 1)\n",
    "            tmp = tmp >> 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return (x ^ y).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def decimalToBinary(num):\n",
    "    s = ''\n",
    "    while num != 0:\n",
    "        remainder = num % 2\n",
    "        s = str(remainder) + s\n",
    "        num = num // 2\n",
    "    return s\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        num = x ^ y\n",
    "        ans = 0\n",
    "        for c in decimalToBinary(num):\n",
    "            if c == '1':\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        cnt = 0\n",
    "        s = x ^ y\n",
    "        while s:\n",
    "            s &= (s-1)\n",
    "            cnt += 1\n",
    "\n",
    "        return cnt \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "\n",
    "        diff = x ^ y\n",
    "        ans = 0\n",
    "        while diff:\n",
    "            ans += diff & 1\n",
    "            diff = diff >> 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        xor = x^y\n",
    "        res = 0\n",
    "\n",
    "        while xor!=0:\n",
    "            res+=1\n",
    "            xor = xor&(xor-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        count = 0\n",
    "        diff_num = x^y\n",
    "        while diff_num != 0:\n",
    "            # print(diff_num)\n",
    "            count += diff_num & 1\n",
    "            diff_num = diff_num >> 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        x = str(bin(x)).replace('0b','')\n",
    "        y = str(bin(y)).replace('0b', '')\n",
    "        length_x = len(x)\n",
    "        length_y = len(y)\n",
    "        if length_x < length_y:\n",
    "            x = '0'*(length_y-length_x)+x\n",
    "        else:\n",
    "            y = '0'*(length_x - length_y)+y\n",
    "        length = len(x)\n",
    "        index = 0\n",
    "        ans = 0\n",
    "        print(x, y)\n",
    "        while index<length:\n",
    "            if x[index] != y[index]:\n",
    "                ans += 1\n",
    "            index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(31):\n",
    "            if (x >> i & 1) != (y >> i & 1):\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        yh = x ^ y\n",
    "        yhstr = str(bin(yh))[2:]\n",
    "        diff = 0\n",
    "        for bit in yhstr:\n",
    "            if bit == '1':\n",
    "                diff += 1\n",
    "\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        z = x^y\n",
    "        ans = 0\n",
    "        while z:\n",
    "            ans+=1\n",
    "            z=z&(z-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        \n",
    "        i = count = 0\n",
    "        while i < 32:\n",
    "            if (x & 1) != (y & 1):\n",
    "                count += 1\n",
    "            x = x >> 1\n",
    "            y = y >> 1\n",
    "            i += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return (bin(x ^ y)[2:]).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return (x ^ y).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        res = bin(x ^ y)\n",
    "        res = res.count(\"1\")\n",
    "        return res\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return (x^y).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y)[2:].count('1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        xor = x^y\n",
    "        distance = 0\n",
    "        while xor is not 0:\n",
    "            xor = xor&(xor-1)\n",
    "            distance+=1\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')\n",
    "        # bin() 返回一个整数 int 或者长整数 long int 的二进制表示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        res = 0\n",
    "        a = x ^ y\n",
    "        while a > 0:\n",
    "            res += 1\n",
    "            a = a & (a - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        count=0\n",
    "        s1=str(bin(x))[2:]\n",
    "        s2=str(bin(y))[2:]\n",
    "        if len(s1)<len(s2):\n",
    "            s1='0'*(len(s2)-len(s1))+s1\n",
    "        else:\n",
    "            s2='0'*(len(s1)-len(s2))+s2\n",
    "        for i in range(0,len(s1)):\n",
    "            if s1[i]!=s2[i]:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        ret = 0\n",
    "        bx,by = bin(x)[2:].zfill(32),bin(y)[2:].zfill(32)\n",
    "        for i in range(32):\n",
    "            if bx[i] != by[i]:\n",
    "                ret += 1\n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        x=str(bin(x))\n",
    "        y=str(bin(y))\n",
    "        x=x[2::]\n",
    "        y=y[2::]\n",
    "        x=x[::-1]\n",
    "        y=y[::-1]\n",
    "        m=len(x)\n",
    "        n=len(y)\n",
    "        k=0\n",
    "        if m-n>0:\n",
    "            c=m-n\n",
    "            i=0\n",
    "            while i<c:\n",
    "                y=y+'0'\n",
    "                i=i+1\n",
    "        else:\n",
    "            c=n-m\n",
    "            i=0\n",
    "            while i<c:\n",
    "                x=x+'0'\n",
    "                i=i+1\n",
    "        for j in range(max(m,n)):\n",
    "            if x[j]!=y[j]:\n",
    "                k=k+1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        tmp = x^y\n",
    "        res = 0\n",
    "        while tmp:\n",
    "            if tmp % 2 == 1:\n",
    "                res += 1\n",
    "            tmp = tmp // 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        tmp = x ^ y\n",
    "        res = 0\n",
    "        while tmp:\n",
    "            res += 1\n",
    "            tmp &= (tmp-1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        s_x = bin(x).split('b')[1]\n",
    "        s_y = bin(y).split('b')[1]\n",
    "        i = len(s_x) - 1\n",
    "        j = len(s_y) - 1\n",
    "        k = 0\n",
    "        while i >= 0 or j >= 0:\n",
    "            n1 = s_x[i] if i >= 0 else str(0)\n",
    "            n2 = s_y[j] if j >= 0 else str(0)\n",
    "            if n1 != n2:\n",
    "                k += 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        res = x ^ y\n",
    "        count = 0\n",
    "        while res > 0:\n",
    "            count += res & 1\n",
    "            res = res >> 1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        result = 0\n",
    "        z = x^y\n",
    "        flag = 1\n",
    "        while z:\n",
    "            result += 1\n",
    "            z &= z-1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        distance = 0\n",
    "        result = x ^ y\n",
    "        while result != 0:\n",
    "            if result & 1 == 1:\n",
    "                distance += 1\n",
    "            result >>= 1\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return (bin(x ^ y)[2:]).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        x = x ^ y\n",
    "        res = 0\n",
    "        while x:\n",
    "            x &= x - 1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "      bx=bin(x)[2:].zfill(32)\n",
    "      by=bin(y)[2:].zfill(32)\n",
    "      res=0\n",
    "      for i in range(32):\n",
    "        if bx[i]!=by[i]:\n",
    "          res+=1\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        # return bin(x ^ y).count('1')\n",
    "\n",
    "        # 自己造轮子\n",
    "        # z, ans = x ^ y, 0\n",
    "        # while z:\n",
    "        #     ans += z & 1\n",
    "        #     z >>= 1\n",
    "        # return ans\n",
    "\n",
    "        # Brian Kernighan 算法\n",
    "        z, ans = x ^ y, 0\n",
    "        while z:\n",
    "            z &= z - 1 # f(x) = x & (x − 1) 为 x 删去其二进制表示中最右侧的 1 的结果\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        n = x ^ y\n",
    "        w = 0\n",
    "        while n > 0:\n",
    "            n = n & (n - 1)\n",
    "            w += 1\n",
    "        return w\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import xor, rshift, mod\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        z = xor(x, y)\n",
    "        count = 0\n",
    "        while z:\n",
    "            if z & 1:\n",
    "                count += 1\n",
    "            z = rshift(z, 1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x ^ y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        # return bin(x ^ y).count('1')\n",
    "\n",
    "        # 自己造轮子\n",
    "        z, ans = x ^ y, 0\n",
    "        while z:\n",
    "            ans += z & 1\n",
    "            z >>= 1\n",
    "        return ans\n",
    "\n",
    "        # Brian Kernighan 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return format(x ^ y, 'b').count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        s_x = bin(x).split('b')[1]\n",
    "        s_y = bin(y).split('b')[1]\n",
    "        i = len(s_x) - 1\n",
    "        j = len(s_y) - 1\n",
    "        k = 0\n",
    "        while i >= 0 or j >= 0:\n",
    "            n1 = s_x[i] if i >= 0 else str(0)\n",
    "            n2 = s_y[j] if j >= 0 else str(0)\n",
    "            if n1 != n2:\n",
    "                k += 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        x = x ^ y\n",
    "        res = 0\n",
    "        while x:\n",
    "            x &= x - 0b1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        return bin(x^y).count('1')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        x_b=self.convertBinary(x)\n",
    "        y_b=self.convertBinary(y)\n",
    "        if len(x_b)>=len(y_b):\n",
    "            y_b=(len(x_b)-len(y_b))*'0'+y_b\n",
    "        else:\n",
    "            x_b=(len(y_b)-len(x_b))*'0'+x_b\n",
    "        ans=0\n",
    "        for i in range(len(x_b)):\n",
    "            if x_b[i]!=y_b[i]:\n",
    "                ans+=1\n",
    "        return ans\n",
    "    def convertBinary(self,num):\n",
    "        res=''\n",
    "        v=1\n",
    "        while v<=num//2:\n",
    "            v*=2\n",
    "        while v>0:\n",
    "            if num<v:\n",
    "                res+='0'\n",
    "            else:\n",
    "                res+='1'\n",
    "                num-=v\n",
    "            v//=2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingDistance(self, x: int, y: int) -> int:\n",
    "        count = 0\n",
    "        while(x!=0 or y!=0):\n",
    "            if(x%2 != y%2):\n",
    "                count += 1\n",
    "            x //= 2\n",
    "            y //= 2\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
